// 斐波那契数，通常用 F(n) 表示，形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：


#include<bits/stdc++.h>
using namespace std;

long long fib(int n){
    if(n==0){
        return 0;
    }
    if(n<3){
        return 1;
    }
    vector<long long> dp(n+1,0);
    dp[0]=0;
    dp[1]=1;
    dp[2]=1;
    for(int i=3;i<=n;++i){
        dp[i]=dp[i-1]+dp[i-2];
    }
    return dp[n];
}

int main(int argc, char const *argv[])
{
    cout<<fib(4)<<endl;
    return 0;
}
